package com.cet.qz.unit01.chapter1_3;

/**
 * @program: algorithm
 * @description: 自定义链表类
 * @author: 陈恩涛
 * @create: 2021-04-09 22:59
 **/
public class Qz1_3_19 {

    public static void main(String[] args) {
        MyLink<Integer> link = new MyLink<>();
        link.addNode(1);
        link.addNode(2);
        link.addNode(3);
        link.addNode(4);
        link.delTailNodeOfLink();
        link.delete(1);
        System.out.println(link);
        System.out.println(link.find(2));
    }
}

class MyLink<Item> {

    private Node first;
    private int n;

    private class Node {
        private Item item;
        private Node next;
    }

    public Node getFirst() {
        return first;
    }

    public boolean isEmpty() {
        return first == null;
    }

    // 链表表头添加一个新的结点
    public void addNode(Item i) {
        Node temp = first;
        first = new Node();
        first.item = i;
        first.next = temp;
        n++;
    }

    /**
     *方法描述： 删除链表最后一个元素
     *
     * @param
     * @return void
     * @author chenentao
     * @date 2021/4/10 22:53
     */
    public void delTailNodeOfLink() {

        if (first == null) {
            System.out.println("链表为空，无法删除节点！");
        } else if (first.next == null) {
            //当前链表只有一个节点
            first = null;
            n--;
        } else {
            Node tail = first;
            while (tail.next.next != null){
                tail = tail.next;
            }
            tail.next =null;
            n--;
        }
    }

    /**
     *方法描述： 删除链表的第k个元素
     *
     * @param k
     * @return void
     * @author chenentao
     * @date 2021/4/11 20:57
     */
    public void delete(int k) {
        if (k > n) {
            throw new RuntimeException("Index is out of bounds!");
        }
        if (k <= 0) {
            throw new RuntimeException("paramater required a Positive integer");
        }
        if (k == 1) {
            first = first.next;
            n--;
        } else {
            Node tmp = first;
            while (k > 2) {
                tmp = tmp.next;
                k--;
            }
            tmp.next = tmp.next.next;
            n--;
        }
    }

    /**
     *方法描述： 判断链表中是否尊在该key值
     *
     * @param key
     * @return boolean
     * @author chenentao
     * @date 2021/4/11 20:59
     */
    public boolean find(Item key) {

        Node tmp = first;
        while (tmp != null) {
            if (key == tmp.item) {
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }


    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        for (Node x = first; x != null; x = x.next) {
            str.append(x.item);
            str.append(" ");
        }
        return str.toString();
    }
}
